//
// Created by 孙代宇 on 2021/12/29.
//

#include "LinkedStack.h"
#include "stdio.h"
LinkedStack linkedStack;

/**
 * P79.3.2
 * 通过对1)的分析，写出一个算法，判定所给的操作序列是否合法。若合法，返回 true，
 * 否则返回 false（假定被判定的操作序列已存入一维数组中）。
 * @param operation 操作数组
 * @param length 数组长度
 * @return 是否合法
 */
bool PushPopIsLegal(char *operation, int length){
    int legalNum = 0;
    for (int i = 0; i < length; ++i) {
        if (legalNum < 0) return false;
        operation[i] == 'I' ? legalNum ++ : legalNum--;
    }
    return true;
}

/**
 * P79.4
 * 设单链表的表头指针为 L，结点结构由 data 和 next 两个域构成，其中 data 域为字符型。
 * 试设计算法判断该链表的全部 n 个字符是否中心对称。例如 xyx、xyyx 都是中心对称。
 * @param list 进行操作的列表
 * @param operation 操作数
 * @param length 操作数长度
 * @return 是否中心对称
 */
bool LinkedDataIsLegal(LinkedStack &list, int *operation, int length){
    int value;
    int param;

    /**
     * 先将一半的操作数入栈
     * 栈为先进后出，例如
     * 进栈顺序         1，2，3，4，
     * 出栈顺序         4，3，2，1，
     * 利用这个特性可以与接下来的一半进行出栈比较
     * 例如
     * 进栈           1，2，3，4
     * 剩下的操作数    4，3，2，1
     * 出栈并依次和剩下的操作数比较，一一对应说明对称
     */
    for (int i = 0; i < length / 2; i++) {
        list.PushElement(linkedStack.list, operation[i]);
    }

    for (int i = 0; i < length / 2; i++) {
        if (length % 2 == 0){
            value = operation[length / 2 + i];

            //  如果操作数长度为单数，则中间的数不进行比较，遍历顺序依次 +1
        } else{
            value = operation[length / 2 + i + 1];
        }
        list.PopElement(linkedStack.list, param);

        if (value != param) return false;
    }

    return true;
}

int main(){
    linkedStack.InitLinkedStack(linkedStack.list);
    int *params = (int *)malloc(sizeof(int) * 3);
    params[0] = 1;
    params[1] = 2;
    params[2] = 1;

//    params[7] = 8;
    printf("%d\n", LinkedDataIsLegal(linkedStack, params, 3));
//    linkedStack.PushElement(linkedStack.list,1);
//    linkedStack.PushElement(linkedStack.list,2);
//    linkedStack.PushElement(linkedStack.list,3);
//    int value;
//    linkedStack.PopElement(linkedStack.list,value);
//    printf("%d\n", value);
//    linkedStack.PeekElement(linkedStack.list,value);
//    printf("%d\n", value);
//    linkedStack.PeekElement(linkedStack.list,value);
//    printf("%d\n", value);
//    linkedStack.PopElement(linkedStack.list,value);
//    printf("%d\n", value);
//    linkedStack.PopElement(linkedStack.list,value);
//    printf("%d\n", value);
//    linkedStack.PopElement(linkedStack.list,value);
//
//    char *params = (char *)malloc(sizeof(char) * 8);
//    params[0] = 'I';
//    params[1] = 'I';
//    params[2] = 'I';
//    params[3] = 'O';
//    params[4] = 'O';
//    params[5] = 'I';
//    params[6] = 'O';
//    params[7] = 'O';
//    printf("%d\n", PushPopIsLegal(params,8));

    return 0;
}